package 牛客.排序;/*
 *@Author: helen
 *@Date:   2021/4/18 10:55
 *@Description:
 题目描述
    给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，
    则最小的4个数字是1,2,3,4。如果K>数组的长度，那么返回一个空的数组
    示例1
        输入      [4,5,1,6,2,7,3,8],4
        返回值    [1,2,3,4]
 */

import java.util.ArrayList;
import java.util.SortedMap;
import java.util.TreeMap;

public class 最小的k个数 {
    //解法一：需要修改原数据
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if(input.length < k || k <= 0)
            return list;
        Partition(input, 0, input.length - 1);
        for (int i = 0; i < k; i++) {
            list.add(input[i]);
        }
        return list;
    }
    public void Partition(int[] input, int start, int end){
        if(start < end){
            int i = start, j = end;
            while (i < j){
                while (i < j &&input[i] <= input[j]) j--;
                if(i < j){
                    int temp = input[i];
                    input[i] = input[j];
                    input[j] = temp;
                    i++;
                }
                while (i < j && input[i] <= input[j]) i++;
                if(i < j){
                    int temp = input[i];
                    input[i] = input[j];
                    input[j] = temp;
                    j--;
                }
            }
            Partition(input, i+1, end);
            Partition(input, start, i - 1);
        }
    }

    //解法2：适合处理海量数据，不用修改原数据
    public ArrayList<Integer> GetLeastNum(int[] input, int k){
        ArrayList<Integer> list = new ArrayList<>();
        if(input.length < k || k <= 0)
            return list;
        SortedMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < input.length; i++) {
            int num = input[i];
            if(i < k) {
                map.put(num, num);
                list.add(num);
            } else if(num < map.lastKey()){
                list.remove(map.lastKey());
                map.remove(map.lastKey());
                map.put(num, num);
                list.add(num);
            }
        }
        return list;
    }

    public static void main(String[] args) {
        最小的k个数 obj = new 最小的k个数();
        int a[] = {4,5,1,6,2,7,3,8};
        int k = 4;
//        ArrayList<Integer> list = obj.GetLeastNumbers_Solution(a, k);
//        System.out.println(list);
        System.out.println(obj.GetLeastNum(a,k));
    }


}
